package _1588_Sum_of_All_Odd_Length_Subarrays;

/**
 * Date: 2021/8/29 09:50
 * Content:
 * 执行用时：1 ms, 在所有 Java 提交中击败了62.96%的用户
 * 内存消耗：36 MB, 在所有 Java 提交中击败了73.48%的用户
 */
public class Solution {

    public int sumOddLengthSubarrays(int[] arr) {
        int n = arr.length;
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + arr[i - 1];

        int res = 0;
        for (int len = 1; len <= n; len += 2)
            for (int i = 1; i + len - 1 <= n; i++) {
                int j = i + len - 1;
                res += sum[j] - sum[i - 1];
            }
        return res;
    }

    public static void main(String[] args) {

        int[] arr = {1, 4, 2, 5, 3};
        System.out.println((new Solution()).sumOddLengthSubarrays(arr));  // 58
    }
}
